#include <stdio.h>
#include <vector>
using namespace std;
#define N 32
vector <int> m[N];
int n, k, v[N], w[N], u[N], b[N], e[N];
void dfs(int i)
{
	int j;
	u[i]=1;
	v[i]=1<<i;
	for(j=0; j<m[i].size(); v[i]|=v[m[i][j]], j++)
		if(!u[m[i][j]]) dfs(m[i][j]);
}
int brute()
{
	int i, j, h, bh, bj;
	for(bj=k+1, h=(1<<k)-1; h>=0; h--)
	{
		for(i=0; i<n; m[i].clear(), i++);
		for(i=0; i<k; i++)
			if((h>>i)&1) m[b[i]].push_back(e[i]);
		for(i=0; i<n; u[i]=0, i++);
		for(i=0; i<n; i++)
			if(!u[i]) dfs(i);
		if(h==(1<<k)-1)
			for(i=0; i<n; w[i]=v[i], i++);
		for(i=0; i<n && v[i]==w[i]; i++);
		if(i==n)
		{
			for(j=0, i=0; i<k; j+=(h>>i)&1, i++);
			if(j<bj) { bh=h; bj=j; }
		}
	}
	return bh;
}
vector <int> q[N];
int s[N][N/32], z;
void dfs2(int i)
{
	int j, t, l;
	u[i]=1;
	for(j=0; j<m[i].size(); j++)
	{
		l=m[i][j];
		if(!u[l]) dfs2(l);
		for(t=0; t<z; s[i][t]|=s[l][t], t++);
	}
	for(j=0; j<m[i].size(); j++)
	{
		l=m[i][j];
		if(!((s[i][l>>5]>>(l&31))&1)) q[i].push_back(l);
		s[i][l>>5]|=1<<(l&31);
	}
}
int sol()
{
	int i, j, l, r;
	for(i=0; i<n; m[i].clear(), q[i].clear(), i++);
	for(i=0; i<k; m[b[i]].push_back(e[i]), i++);
	z=(n+31)/32;
	for(i=0; i<n; u[i]=0, i++)
		for(j=0; j<z; s[i][j]=0, j++);
	for(i=0; i<n; i++)
		if(!u[i]) dfs2(i);
	for(r=0, i=0; i<n; i++)
		for(j=0; j<q[i].size(); j++)
		{
			for(l=0; l<k && (i!=b[l] || q[i][j]!=e[l]); l++);
			r|=1<<l;
		}
	return r;
}
int main()
{
	int i, j, l, u[N][N];
	for(n=6, k=8; ; )
	{
		for(i=0; i<n; i++)
			for(j=0; j<n; u[i][j]=0, j++);
		for(l=0; l<k; )
		{
			i=rand()%n;
			j=rand()%n;
			if(i==j) continue;
			if(j<i) swap(i, j);
			if(u[i][j]) continue;
			u[i][j]=1;
			b[l]=i;
			e[l]=j;
			l++;
		}
		if(sol()!=brute()) throw;
		else printf("!");
	}
	return 0;
}